package com.lh.jianzhioffer.专项练习.链表;

/**
 * @author: linghao
 * @since: 2023/3/11
 *
 * 多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
 *
 * 给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中
 *输入：head = [1,2,null,3]
 * 输出：[1,3,2]
 * 解释：
 *
 * 输入的多级列表如下图所示：
 *
 *   1---2---NULL
 *   |
 *   3---NULL
 *
 *   递归进行深度优先搜索
 *   看做树的前序遍历  root child next
 */
public class 展平多级双向链表028 {

    public Node flatten(Node head) {
        if(head == null)return head;
        dfs(head);
        return head;
    }

    Node pre = null;
    private void dfs(Node head) {
        if(head == null)return;
        Node next = head.next;
        if(pre != null){
            pre.next = head;
        }
        head.prev = pre;
        pre = head;
        dfs(head.child);
        head.child = null;
        dfs(next);
    }


    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }
}
